import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * User: tsegelskyi
 */

public class RandomizedQueue<Item> implements Iterable<Item> {
    private Item[] items;
    private int N;
    private int arraySize;

    public RandomizedQueue() {
        items = (Item[]) (new Object[1]);
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void enqueue(Item item) {
        if (item == null)
            throw new NullPointerException();
        if (arraySize == items.length)
            resize(2 * items.length);
        items[arraySize++] = item;
        N++;
    }

    private void resize(int capacity) {
        Item[] copy = (Item[]) new Object[capacity];
        int oldJ = 0;
        int k = 0;
        for (int i = 0; i < arraySize; i++) {
            int j = i + oldJ;
            while (j < arraySize && items[j] == null)
                j++;
            oldJ = j - i;
            if (k < N) {
                copy[i] = items[j];
                k++;
            } else
                break;

        }
        arraySize = N;
        items = copy;
    }

    public Item dequeue() {
        if (isEmpty())
            throw new NoSuchElementException();
        if (N > 0 && N <= items.length / 4)
            resize(items.length / 4);
        int returnIndex = StdRandom.uniform(arraySize);
        while (items[returnIndex] == null)
            returnIndex = StdRandom.uniform(arraySize);
        Item item = items[returnIndex];
        items[returnIndex] = null;
        N--;
        return item;
    }

    public Item sample() {
        if (isEmpty())
            throw new NoSuchElementException();
        int returnIndex = StdRandom.uniform(arraySize);
        while (items[returnIndex] == null)
            returnIndex = StdRandom.uniform(arraySize);
        Item item = items[returnIndex];
        return item;
    }

    @Override
    public Iterator<Item> iterator() {
        return new RandomizedQueueIterator();
    }

    private class RandomizedQueueIterator implements Iterator<Item> {
        int i = 0;
        int[] returnIndex;
        public RandomizedQueueIterator() {
            resize(N);
            returnIndex = new int[N];
            for (int i = 0; i < N; i++) {
                returnIndex[i] = i;
            }
            for (int i = 0; i < N; i++) {
                int r = StdRandom.uniform(i + 1);
                int temp = returnIndex[i];
                returnIndex[i] = returnIndex[r];
                returnIndex[r] = temp;
            }
        }

        @Override
        public boolean hasNext() {
            return i < N;
        }

        @Override
        public Item next(){
            if (i >= N)
                throw new NoSuchElementException();
            return items[returnIndex[i++]];
        }

        @Override
        public void remove(){
            throw new UnsupportedOperationException("This operation is not supported");
        }
    }

    public static void main(String[] args) {
        RandomizedQueue<Integer> test = new RandomizedQueue<Integer>();
        test.enqueue(1);
        test.enqueue(2);
        test.enqueue(3);
        test.enqueue(4);
        Iterator iterator = test.iterator();
        for (Integer i:test)
            System.out.println(i);
    }

}
